package com.sunkq.algorithms;

import java.util.HashMap;
import java.util.Map;

public class TreedNodeTest3 {

    public static void main(String[] args) {
        TreedNodeTest3 test = new TreedNodeTest3();
        int[] nums = new int[]{3,2,1,6,0,5};
        TreeNode root = test.constructMaximumBinaryTree(nums);
        while (root!=null){

            System.out.println(root.val);
            root = root.right;
        }
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums,0,nums.length-1);
    }

    TreeNode build(int [] nums,int start, int end){
//        if(start>end){
//            return null;
//        }

        if (start > end) { return null; }

//        int index = -1,maxVal = Integer.MIN_VALUE;
//        for (int i = start; i < end; i++) {
//            if(maxVal<nums[i]){
//                index = i;
//                maxVal = nums[i];
//            }
//        }

        int index = -1, maxVal = Integer.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }

        TreeNode root = new TreeNode(maxVal);

        root.left = build(nums,start,index-1);
        root.right = build(nums,index+1,end);
        return root;
    }


    Map<Integer,Integer> indexMap = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i],i);
        }
        return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    TreeNode build(int[] inorder,int inStart,int inEnd, int[] postorder,int postStart,int postEnd){
        if(inStart>inEnd){
            return null;
        }
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = indexMap.get(rootVal);
        int leftSize = rootIndex-inStart;

        root.left = build(inorder,inStart,rootIndex-1,postorder,postStart,postStart+leftSize-1);
        root.right = build(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}

